'''
https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/description/?envType=study-plan-v2&envId=graph-theory
'''
from collections import defaultdict, deque
from typing import List


class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

        n = len(colors)
        dp = [[0] * 26 for _ in range(n)]
        q = deque([u for u in range(n) if indegree[u] == 0])
        visited = 0
        while q:
            u = q.popleft()
            visited += 1
            dp[u][ord(colors[u]) - ord('a')] += 1
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
                for c in range(26):
                    dp[v][c] = max(dp[v][c], dp[u][c])
        if visited != n:
            return -1
        return max(max(row) for row in dp)

colors = "abaca"
edges = [[0,1],[0,2],[2,3],[3,4]]
print(Solution().largestPathValue(colors, edges))